package com.buddy.summary.code.tree;

import org.junit.Test;

/**
 * 查找二叉树
 * 对于树中每个节点node，它的左子树中的所有项都小于node的项
 * 右子树中的所有项都大于node1的项
 * @param <AnyType>
 */
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
    private static class BinaryNode<AnyType>{
        AnyType element;
        BinaryNode left;
        BinaryNode right;

        BinaryNode(AnyType element) {
            this(element,null,null);
        }

        BinaryNode(AnyType element, BinaryNode left, BinaryNode right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }

    private BinaryNode<AnyType> root;

    public BinarySearchTree(){
        root = null;
    }

    public void makeEmpty(){
        root = null;
    }

    public boolean isEmpty(){
        return root == null;
    }

    public boolean contains(AnyType x){
        return contains(x,root);
    }
    public AnyType findMin(){
        if (isEmpty()) return null;
        return findMin(root).element;
    }
    public AnyType findMax(){
        if (isEmpty()) return null;
        return findMax(root).element;
    }

    public void insert(AnyType x){
        root = insert(x,root);
    }

    public void remove(AnyType x){
        root = remove(x,root);
    }

    public void printTree(){
        if (isEmpty())
            System.out.println("Empty Tree");
        else printTree(root);
    }

    private boolean contains(AnyType x,BinaryNode<AnyType> node){
        if (node == null){
            return false;
        }
        int compareResult = x.compareTo(node.element);
        if (compareResult < 0)
            return contains(x,node.left);
        else if(compareResult > 0)
            return contains(x,node.right);
        else
            return true;
    }

    private BinaryNode<AnyType> findMin(BinaryNode<AnyType> node){
        if (node == null)
            return null;
        else if (node.left == null)
            return node;
        return findMin(node.left);
    }

    private BinaryNode<AnyType> findMax(BinaryNode<AnyType> node){
        if (node != null)
            while (node.right != null)
                node = node.right;
        return node;
    }

    private BinaryNode<AnyType> insert(AnyType x,BinaryNode<AnyType> node){
        if (node == null)
            return new BinaryNode<>(x,null,null);
        int compareResult = x.compareTo(node.element);
        if (compareResult < 0)
            node.left = insert(x,node.left);
        else if (compareResult > 0)
            node.right = insert(x,node.right);
        return node;
    }

    private BinaryNode<AnyType> remove(AnyType x,BinaryNode<AnyType> node){
        if (node == null){
            return node;
        }
        int compareResult = x.compareTo(node.element);
        if (compareResult < 0)
            node.left = remove(x,node.left);
        else if (compareResult > 0)
            node.right = remove(x,node.right);
        else if (node.left != null && node.right != null){
            node.element = (AnyType) findMin(node.right).element;//使用右子树最小的代替当前，因为最小的节点没有左子树
            node.right = remove(node.element,node.right);
        }else{
            node = (node.left != null)?node.left:node.right;
        }
        return node;
    }

    private void printTree(BinaryNode<AnyType> node){
        if (node != null){
            printTree(node.left);
            System.out.println(node.element);
            printTree(node.right);
        }
    }



    @Test
    public void binarySearchTreeTest(){
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        //调用insert方法
        for (int i = 0;i<10;i++){
            binarySearchTree.insert((int) (Math.random()*100));
        }
        //打印
        binarySearchTree.printTree();
        //插入数据
        binarySearchTree.insert(101);
        binarySearchTree.printTree();
        System.out.println(binarySearchTree.findMax());
        System.out.println(binarySearchTree.findMin());
        System.out.println(binarySearchTree.contains(0));
        binarySearchTree.remove(binarySearchTree.findMin());
        System.out.println(binarySearchTree.findMin());
    }
}


